type Lazy<T> = () => T;
function lazy<T>(x: T): Lazy<T> { return () => x }

type LazyList<T> = Lazy<{
    head: Lazy<T>,
    tail: LazyList<T>
} | null>

function toList<T>(xs: T[]): LazyList<T> {
    return () => {
        if (xs.length === 0) {
            return null;
        }
        return {
            head: lazy(xs[0]),
            tail: toList(xs.slice(1))
        };
    }
}

function range(first: Lazy<number>): LazyList<number> {
    return () => {
        const x = first();
        return {
            head: lazy(x),
            tail: range(lazy(x + 1))
        };
    }
}

function printList<T>(xs: LazyList<T>) {
    let pair = xs();
    while (pair != null) {
        console.log(pair.head());
        pair = pair.tail();
    }
}

printList(toList([1, 2, 3, 4, 5]));

console.log("===========")

// printList(range(() => 10))

function take<T>(n: Lazy<number>, xs: LazyList<T>): LazyList<T> {
    return () => {
        let m = n();
        let pair = xs()
        if (m === 0) {
            return null
        }
        if (pair === null) {
            return null
        }
        return {
            head: pair.head,
            tail: take(lazy(m - 1), pair.tail)
        }
    }
}

printList(take(lazy(100), range(lazy(10))))

console.log("===========")

function filter<T>(f: (x: T)=> boolean, xs: LazyList<T>): LazyList<T> {
    return () => {
        let pair = xs();
        if (pair === null) {
            return null
        }
        let x = pair.head()
        if (f(pair.head())) {
            return {
                head: lazy(x),
                tail: filter(f, pair.tail)
            }
        }
        return filter(f, pair.tail)()
    }
}

printList(
    take(lazy(10), 
        filter(x=> x%2===0, 
            range(lazy(10)))))



console.log("===========")



function sieve(xs: LazyList<number>): LazyList<number> {
    return () => {
        let pair = xs()
        if (pair == null) {
            return null
        }
        let y = pair.head()
        return {
            head: lazy(y),
            tail: sieve(filter((x) => x % y !== 0, pair.tail))
        }
    }
}

const prime = sieve(range(lazy(2)))

printList(prime)


const cons = <T>(x: Lazy<T>) => (ys: LazyList<T>): LazyList<T> => {
    return () => {
        let pair = ys()
        return {
            head: x,
            tail: () => pair
        }
    }
}



const next = (n: Lazy<number>) => (x: Lazy<number>): Lazy<number> => lazy((x() + n() / x()) / 2);

const repeat = (f: (x: Lazy<number>) => Lazy<number>) => (x: Lazy<number>): LazyList<number> => cons(x)(repeat(f)(f(x)))
